// LeetCode 主站 Problem Nr. 23: 合并 K 个升序链表

/*
给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：
	输入：lists = [[1,4,5],[1,3,4],[2,6]]
	输出：[1,1,2,3,4,4,5,6]
	解释：链表数组如下：
		[
  			1->4->5,
  			1->3->4,
  			2->6
		]
	将它们合并到一个有序链表中得到：
		1->1->2->3->4->4->5->6
示例 2：
	输入：lists = []
	输出：[]
示例 3：
	输入：lists = [[]]
	输出：[]

提示：
    k == lists.length
    0 <= k <= 10^4
    0 <= lists[i].length <= 500
    -10^4 <= lists[i][j] <= 10^4
    lists[i] 按 升序 排列
    lists[i].length 的总和不超过 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import (
	"fmt"

	"github.com/saint-yellow/think-leetcode/ds"
)

type ListNode = ds.SinglyLinkedNode[int]

func mergeKLists(lists []*ListNode) *ListNode {
	return method1(lists)
}

// 两两合并，时间复杂度为平方级别
func method1(lists []*ListNode) *ListNode {
	var result *ListNode
	for _, list := range lists {
		result = mergeTwoLists(result, list)
	}
	return result
}

func mergeTwoLists(list1, list2 *ListNode) *ListNode {
	if list1 == nil || list2 == nil {
		if list1 != nil {
			return list1
		} else if list2 != nil {
			return list2
		} else {
			return nil
		}
	}

	sentinel := &ListNode{Val:-1}
	p0 := sentinel
	p1, p2 := list1, list2

	for p1 != nil && p2 != nil {
		np1, np2 := p1.Next, p2.Next
		if p1.Val == p2.Val {
			p0.Next = p1
			p0.Next.Next = p2
			p0 = p0.Next.Next

			p1 = np1
			p2 = np2
		} else if p1.Val < p2.Val {
			p0.Next = p1
			p0 = p0.Next

			p1 = np1
		} else {
			p0.Next = p2
			p0 = p0.Next

			p2 = np2
		}
	}

	if p1 != nil {
		p0.Next = p1
	}

	if p2 != nil {
		p0.Next = p2
	}

	return sentinel.Next
}

func main() {
	lists := []*ListNode{
		ds.BuildSinglyLinkedList([]int{}),
		// ds.BuildSinglyLinkedList([]int{1,4,5}),
		// ds.BuildSinglyLinkedList([]int{1,3,4}),
		// ds.BuildSinglyLinkedList([]int{2,6}),
	}
	fmt.Println(mergeKLists(lists).ToList())
}
